package com.icbc.DataStructuresAndAlgorithms;

import java.util.Arrays;

/**
 * 背包问题
 */
public class KnapsackProblem {
	public static void main(String[] args) {
		//首先将物品的重量数组创建
		int[] w = {0 , 1 , 4 , 3};
		//创建对应物品的价值
		int[] val = {0 , 1500 ,3000 ,2000};
		//定义背包的容量,这里背包容量应为4,但背包容量在填报时会有5种情况
		int m = 5;
		//创建填报表
		int[][] v = new int[w.length][m];
		//path是用于查看最后哪几个商品放入的背包中
		int[][] path = new int[w.length][m];
		//初始化填报表中的第一行和第一列,这里不做处理了,因为默认就是0
		
		//将填报表进行循环
		for (int i = 1; i < v.length; i++) {
			int[] ints = v[i];
			for (int j = 1; j < ints.length; j++) {
				if (w[i] > j){
					v[i][j] = v[i - 1][j];
				} else if (j >= w[i]) {
					if (v[i - 1][j] > val[i] + v[i - 1][j - w[i]]){
						v[i][j] = v[i - 1][j];
					}else{
						v[i][j] = val[i] + v[i - 1][j - w[i]];
						path[i][j] = 1;
					}
				}
			}
		}
		//打印v
		Arrays.stream(v).forEach(a -> System.out.println(Arrays.toString(a)));
		//打印v[3][4]
		System.out.println(v[3][4]);
		
		int i = path.length - 1;
		int j = path[0].length - 1;
		while (i > 0 && j > 0){
			if (path[i][j] == 1){
				System.out.println("第"+i+"个商品加入背包");
				j -= w[i];
			}
			i--;
		}
	}
}
